#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;

#define INF 1000.0

#define TRACE(x...) 
#define PRINT(x...) TRACE(printf(x))

int army[30010];
int n, m;

typedef struct pt {
	int x, y;
} Pt;

Pt pts[55];
int dist[55][55];
int median;
int d;
bool vis[55];

inline int getD2(Pt a, Pt b) {
	return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

void dfs(int a) {
	vis[a]=true;

	for (int i=0; i<m; i++) {
		if (dist[a][i] && !vis[i]) dfs(i);
	}
}

int main() {
	scanf("%d %d", &n, &m);

	while (n!=-1 && m!=-1) {
		for (int i=0; i<n; i++) scanf("%d", &army[i]);
		for (int i=0; i<m; i++) scanf("%d %d", &pts[i].x, &pts[i].y);

		sort(army, army+n);

		for (int i=0; i<m; i++)
			for (int j=0; j<m; j++) dist[i][j]=0;
		
		median=army[(n/2)]; //conferir
		median*=median;
		
		for (int i=0; i<m; i++) 
			for (int j=0; j<m; j++) {
				if (i==j) continue;
				d=getD2(pts[i], pts[j]);
				
				if (d<=median) {
					dist[i][j]=dist[j][i]=d;
				}
			}

		TRACE (
		for (int i=0; i<m; i++) {
			for (int j=0; j<m; j++)
				printf("%d ", dist[i][j]);

			printf("\n");
		}
		);

		for (int i=0; i<m; i++) vis[i]=false;

		dfs(0);	

		if (vis[1]) printf("NOT valid\n");
		else printf("valid\n");

		TRACE (
		for (int i=0; i<m; i++) 
			if (vis[i]) printf("1");
			else printf("0");

		printf("\n");
		);

		scanf("%d %d", &n, &m);	
	}

	return 0;
}
